#include "./linked-list.h"

using namespace std;

void initLinkedList(LinkedList &list)
{
	list = new Node;
	list->data = 0;
	list->next = nullptr;
}

int linkedListEmpty(LinkedList &list)
{
	return list->next == nullptr;
}

int linkedListLength(LinkedList &list)
{
	Node *pointer = list;
	int length = 0;
	while (pointer->next != nullptr)
	{
		length++;
		pointer = pointer->next;
	}
	return length;
}

ElemType getLinkedListElem(LinkedList &list, int i)
{
	Node *pointer = list;
	for (int j = -1; j < i; j++)
	{
		pointer = pointer->next;
	}
	return pointer->data;
}

int locateLinkedListElem(LinkedList &list, ElemType e)
{
	Node *pointer = list;
	int index = -1;
	while (pointer->next != nullptr)
	{
		pointer = pointer->next;
		index++;
		if (pointer->data == e)
		{
			return index;
		}
	}
	return -1;
}

ElemType priorLinkedListElem(LinkedList &list, ElemType e)
{
	int i = locateLinkedListElem(list, e);
	if (i == -1 || i == 0)
	{
		return 0;
	}
	Node *pointer = list;
	for (int j = -1; j < i - 1; j++)
	{
		pointer = pointer->next;
	}
	return pointer->data;
}

ElemType nextLinkedListElem(LinkedList &list, ElemType e)
{
	int i = locateLinkedListElem(list, e);
	if (i == -1 || i == linkedListLength(list) - 1)
	{
		return 0;
	}
	Node *pointer = list;
	for (int j = -1; j < i + 1; j++)
	{
		pointer = pointer->next;
	}
	return pointer->data;
}

void linkedListInsert(LinkedList &list, int i, ElemType e)
{
	Node *pointer = list;
	for (int j = -1; j < i - 1; j++)
	{
		pointer = pointer->next;
	}
	// 新建结点，并把新结点后继指向当前结点后继
	Node *node = new Node;
	node->data = e;
	node->next = pointer->next;
	// 把当前结点后继指向新节点
	pointer->next = node;
}

ElemType linkedListDelete(LinkedList &list, int i)
{
	Node *pointer = list;
	for (int j = -1; j < i - 1; j++)
	{
		pointer = pointer->next;
	}
	ElemType e = pointer->data;
	// 直接把当前节点后继指向下一个的下一个
	pointer->next = pointer->next->next;
	return e;
}

void linkedListReverse(LinkedList &list)
{
	// 双指针，头插法
	// p用于遍历每个结点，q用于遍历后被插入至原链表头
	Node *p = list->next, *q;
	list->next = nullptr;
	while (p != nullptr)
	{
		q = p;
		p = p->next;
		// 把当前节点依次插入到链表头后面
		q->next = list->next;
		list->next = q;
	}
}

void linkedListTraverse(LinkedList &list, void (*visit)(ElemType &))
{
	Node *pointer = list;
	while (pointer->next != nullptr)
	{
		pointer = pointer->next;
		visit(pointer->data);
	}
}